package superbubble.onegraph;

import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class StrongConnectedComponentsFinder {
	private int leader = 0;
	private int[] leader_node;
	private int explore[];
	private int finishing_time_of_node[];
	private int finishing_time = 1;
	private int number_of_nodes;
	private Stack<Integer> stack;
	private Map<Integer, Integer> finishing_time_map;

	public StrongConnectedComponentsFinder(int number_of_nodes) {
		this.number_of_nodes = number_of_nodes;
		leader_node = new int[number_of_nodes + 1];
		explore = new int[number_of_nodes + 1];
		finishing_time_of_node = new int[number_of_nodes + 1];
		stack = new Stack<Integer>();
		finishing_time_map = new HashMap<Integer, Integer>();
	}

	public void strongConnectedComponent(byte adjacency_matrix[][]) {
		for (int i = number_of_nodes; i > 0; i--) {
			if (explore[i] == 0) {
				dfs_1(adjacency_matrix, i);
			}
		}
		int rev_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
		for (int i = 1; i <= number_of_nodes; i++) {
			for (int j = 1; j <= number_of_nodes; j++) {
				if (adjacency_matrix[i][j] == 1)
					rev_matrix[finishing_time_of_node[j]][finishing_time_of_node[i]] = adjacency_matrix[i][j];
			}
		}

		for (int i = 1; i <= number_of_nodes; i++) {
			explore[i] = 0;
			leader_node[i] = 0;
		}

		for (int i = number_of_nodes; i > 0; i--) {
			if (explore[i] == 0) {
				leader = i;
				dfs_2(rev_matrix, i);
			}
		}
	}

	public void dfs_1(byte adjacency_matrix[][], int source) {
		explore[source] = 1;
		stack.push(source);
		int i = 1;
		int element = source;

		while (!stack.isEmpty()) {
			element = stack.peek();
			i = 1;
			while (i <= number_of_nodes) {
				if (adjacency_matrix[element][i] == 1 && explore[i] == 0) {
					stack.push(i);
					explore[i] = 1;
					element = i;
					i = 1;
					continue;
				}
				i++;
			}
			int poped = stack.pop();
			int time = finishing_time++;
			finishing_time_of_node[poped] = time;
			finishing_time_map.put(time, poped);
		}
	}

	public void dfs_2(int rev_matrix[][], int source) {
		explore[source] = 1;
		leader_node[finishing_time_map.get(source)] = leader;
		stack.push(source);
		int i = 1;
		int element = source;
		while (!stack.isEmpty()) {
			element = stack.peek();
			i = 1;
			while (i <= number_of_nodes) {
				if (rev_matrix[element][i] == 1 && explore[i] == 0) {
					if (leader_node[finishing_time_map.get(i)] == 0)
						leader_node[finishing_time_map.get(i)] = leader;
					stack.push(i);
					explore[i] = 1;
					element = i;
					i = 1;
					continue;
				}
				i++;
			}
			stack.pop();
		}
	}

//	public static void main(String... arg) {
//		int number_of_nodes;
//		Scanner scanner = null;
//		try {
//			System.out.println("Enter the number of nodes in the graph");
//			scanner = new Scanner(System.in);
//			number_of_nodes = scanner.nextInt();
//
//			int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
//			System.out.println("Enter the adjacency matrix");
//			for (int i = 1; i <= number_of_nodes; i++)
//				for (int j = 1; j <= number_of_nodes; j++)
//					adjacency_matrix[i][j] = scanner.nextInt();
//
//			StrongConnectedComponentsFinder strong = new StrongConnectedComponentsFinder(
//					number_of_nodes);
//			strong.strongConnectedComponent(adjacency_matrix);
//
//			System.out.println("The Strong Connected Components are");
//			for (int i = 1; i < strong.leader_node.length; i++) {
//				System.out.println("Node " + i + "belongs to SCC"
//						+ strong.finishing_time_map.get(strong.leader_node[i]));
//			}
//		} catch (InputMismatchException inputMismatch) {
//			System.out.println("Wrong Input Format");
//		}
//	}

	public int getLeader() {
		return leader;
	}

	public void setLeader(int leader) {
		this.leader = leader;
	}

	public int[] getLeader_node() {
		return leader_node;
	}

	public void setLeader_node(int[] leader_node) {
		this.leader_node = leader_node;
	}

	public int[] getExplore() {
		return explore;
	}

	public void setExplore(int[] explore) {
		this.explore = explore;
	}

	public int[] getFinishing_time_of_node() {
		return finishing_time_of_node;
	}

	public void setFinishing_time_of_node(int[] finishing_time_of_node) {
		this.finishing_time_of_node = finishing_time_of_node;
	}

	public int getFinishing_time() {
		return finishing_time;
	}

	public void setFinishing_time(int finishing_time) {
		this.finishing_time = finishing_time;
	}

	public int getNumber_of_nodes() {
		return number_of_nodes;
	}

	public void setNumber_of_nodes(int number_of_nodes) {
		this.number_of_nodes = number_of_nodes;
	}

	public Stack<Integer> getStack() {
		return stack;
	}

	public void setStack(Stack<Integer> stack) {
		this.stack = stack;
	}

	public Map<Integer, Integer> getFinishing_time_map() {
		return finishing_time_map;
	}

	public void setFinishing_time_map(Map<Integer, Integer> finishing_time_map) {
		this.finishing_time_map = finishing_time_map;
	}
	
}
